package index.Btree;

import java.io.FileNotFoundException;
import java.io.IOException;

import file_rw.FileRW;
import java.lang.Math;

public class Btree implements BtreeInterface  {

	///////////////<-------------�����ļ�ͷ������----------
	public   int index_size = 30 ; //�����ļ���С
	public   int index_k_n = 299 ; //ÿ���ڵ����Ԫ��
	public   int index_block_empty = 0 ; //���п����
	public   double index_verson = 0.1; //�汾�ţ�0.1V��
	public   int index_root_pagenum = 1 ;///root�ڵ�ҳ��
	public   int  index_date = 20111022; //����
	public   String index_author ="zq+ssy+xnn+zjn"; //(����Ϊ14�ֽ�)�빤��(���� A+B+C+D)(�����100�ֽ�)	
	///////------------------------------------------->
	
	///////////////<-------------�����ļ�ͷ������----------
	@Override
	public int getKn() {
		// TODO Auto-generated method stub
		int i = 0 ;
		FileRW fr = new FileRW();
		try {
			i = fr.readInt(index_file_addr, 0);
		} catch (IOException e) {
			e.printStackTrace();
		}
		return i;
	}

	@Override
	public int getBlockEmpty() {
		// TODO Auto-generated method stub
		int i = 0 ;
		FileRW fr = new FileRW();
		try {
			i = fr.readInt(index_file_addr, (index_head_en));
		} catch (IOException e) {
			e.printStackTrace();
		}
		return i;
	}
	
	@Override
	public double getVerson() {
		// TODO Auto-generated method stub
		double i = 0 ;
		FileRW fr = new FileRW();
		try {
			i = fr.readInt(index_file_addr, (index_head_en+index_head_eb));
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return i;
	}
	
	@Override
	public int getRootNum() {
		// TODO Auto-generated method stub
		int i = 0 ;
		FileRW fr = new FileRW();
		try {
			i = fr.readInt(index_file_addr, (index_head_en+index_head_eb+index_head_verson));
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return i;
	}

	@Override
	public int getDate() {
		// TODO Auto-generated method stub
		int i = 0 ;
		FileRW fr = new FileRW();
		try {
			i = fr.readInt(index_file_addr, (index_head_en+index_head_eb+index_head_verson+index_head_rn));
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return i;
	}

	@Override
	public String getAuthor() {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			index_author = fr.readString(index_file_addr, (index_head_en+index_head_eb+index_head_verson+index_head_rn+index_head_date), 14);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		return index_author;
	}

	@Override
	public void setKn(int i) {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, 0, i);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
	}

	@Override
	public void setBlockEmpty(int i) {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, index_head_en, i);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}				
	}

	@Override
	public void setVerson(double i) {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, index_head_en+index_head_eb,i);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
		
	}
	
	@Override
	public void setRootNum(int i) {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, index_head_en+index_head_eb+index_head_verson, i);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}		
	}

	@Override
	public void setDate(int i) {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, index_head_en+index_head_eb+index_head_verson+index_head_rn, i);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
	}

	@Override
	public void setAuthor(String i) {
		// TODO Auto-generated method stub
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, index_head_en+index_head_eb+index_head_verson+index_head_rn+index_head_date, i);
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}			
	}
	
	@Override
	public void setBtree(int rn, int kn, int bl, double v, int date, String author) {
		// TODO Auto-generated method stub
		Btree bt = new Btree();
		bt.setRootNum(rn);
		bt.setKn(kn);
		bt.setBlockEmpty(bl);
		bt.setVerson(v);
		bt.setDate(date);
		bt.setAuthor(author);
		return ;
	}
	///////------------------------------------------->
	
	//////<------------�ڵ�ռ��λͼ����---------------------
	@Override
	public int getEmptyNode() {
		int i = 0 ;
		FileRW fr = new FileRW();
		try {
			for(int j=1;j!=block_head_bmp;j++){
				i = fr.readInt(index_file_addr, block_head_size+(j-1)*4);
				if(i==0)
					return j;
			}			
		} catch (IOException e) {
			e.printStackTrace();
		}
		return i;
	}

	@Override
	public void setEmptyNode(int i) {
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, block_head_size+(i-1)*4, 1);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	
	public void setEmptyNode(int i,int n) {
		FileRW fr = new FileRW();
		try {
			fr.writeNum(index_file_addr, block_head_size+(i-1)*4, n);
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}
	///////------------------------------------------->
	
	
	//////<------------�ڵ�ľ�����������룬ɾ����ҵȣ�---------------------

	@Override
	public int addNode() {
		// TODO Auto-generated method stub
		int empty = 0;
		Btree bt = new Btree();
		empty = bt.getEmptyNode();
		bt.setEmptyNode(empty);
		return empty;
	}

	@Override
	public int splitNode(int blockID) {
		int vrootid = 0;  // ����ķ��Ѻ�root
		int rightson = 0; //���Ѻ���ҽڵ�
		int elementNum = 0; //��ȡ �ڵ��Ԫ����
		int i;		
		Btree bt = new Btree();	
		vrootid = bt.addNode();    //����һ���ڵ�
		rightson = bt.addNode();   //����һ���ڵ�	
		BtreeNode bnOri = new BtreeNode(blockID);  //ԭʼ�ڵ�	
		BtreeNode bnRight = new BtreeNode(rightson);  //�½��ҽڵ�
		BtreeNode bnRoot = new BtreeNode(vrootid);  //�½�����root�ڵ�			
		elementNum = bnOri.getNum();		
		int[] keys = new int[elementNum]; //��Žڵ��������ݵ�����
		int[] pagenums = new int[elementNum];//��Žڵ����е�ָ�������			
		keys = bnOri.getkey();// ��ȡ�������
		pagenums = bnOri.getPageNum();//��ȡָ������		
		int[] temp_num = new int[elementNum/2];
		int[] temp_page = new int[elementNum/2];		
		for(i=0;i<elementNum/2;i++){
			temp_num[i] = keys[elementNum/2+i];
			temp_page[i] = pagenums[elementNum/2+i];
		}               //���Ѻ󣬿���(n/2 --n)����ݵ��½����ҽڵ�    		
		bnRight.setNode(elementNum/2, bnOri.getRighson(), 1, vrootid, blockID, temp_num, temp_page);
		bnOri.setNode(elementNum/2, rightson, 1, vrootid, -1, null, null);
		
		temp_page[0] = blockID;
		bnRoot.setNode(1, rightson, 0, -1, -1, temp_num, temp_page);	
		return vrootid;

	}
	
	@Override
	public int splitNode2(int blockID,int blockID2) {
		int vrootid = 0;  // ����ķ��Ѻ�root
		int rightson = 0; //���Ѻ���ҽڵ�
		int num,page;	
		Btree bt = new Btree();
		vrootid = bt.addNode();    //����һ���ڵ�
		rightson = blockID2;
		BtreeNode bnOri = new BtreeNode(blockID);  //ԭʼ�ڵ�	
		BtreeNode bnRight = new BtreeNode(rightson);  //�½��ҽڵ�
		BtreeNode bnRoot = new BtreeNode(vrootid);  //�½�����root�ڵ�
				
		num =  bnOri.getKey(bnOri.getNum());
		page = bnOri.getPageNum(bnOri.getNum());
		
		int[] temp = new int[2];
		temp[0]=num;
		int[] temps = new int[2];
		temps[0]=blockID;
		
		bnOri.setNode((bnOri.getNum()-1), page, -1, vrootid, -1, null, null);
		bnRoot.setNode(1, rightson, 0, -1, -1, temp, temps);
		bnRight.setNode(-1, -1, -1, vrootid, -1, null, null);
		
		return vrootid;

	}

	public int splitNodeInter(int blockID,int n,int LblockID,int RblockID){
		int vrootid = 0;  // ����ķ��Ѻ�root
		int rightson = 0; //���Ѻ���ҽڵ�
		int elementNum = 0; //��ȡ �ڵ��Ԫ����
		int i,m=0; //m������ڵڼ�����ݴ�����		
		Btree bt = new Btree();	
		vrootid = bt.addNode();    //����һ���ڵ�
		rightson = bt.addNode();   //����һ���ڵ�
		BtreeNode bnOri = new BtreeNode(blockID);  //ԭʼ�ڵ�	
		BtreeNode bnRight = new BtreeNode(rightson);  //�½��ҽڵ�
		BtreeNode bnRoot = new BtreeNode(vrootid);  //�½�����root�ڵ�
		
		elementNum = bnOri.getNum();		
		int[] keys = new int[elementNum]; //��Žڵ��������ݵ�����
		int[] pagenums = new int[elementNum];//��Žڵ����е�ָ�������	
		
		keys = bnOri.getkey();// ��ȡ�������
		pagenums = bnOri.getPageNum();//��ȡָ������		
		//�ҵ�����λ��==m
		
		for(i=0;i<elementNum;i++){
			if(keys[i]>n){
				m=i;
				break;
			}
		}	
		
		int[] temp = new int[elementNum-m+2];
		int[] temps = new int[elementNum-m+2];
		
		for(i=0;i<elementNum-m;i++){
			temp[i]=keys[i+m];
		}		       //���Ѻ󣬿���(n --��β)����ݵ��½����ҽڵ�    
		for(i=0;i<elementNum-m;i++){
			temps[i]= pagenums[i+m];
		}	
		

		temps[0] = blockID;
		
		bnRight.setNode(elementNum-m,  bnOri.getRighson(), 0, vrootid, -1, temp, temps);
		
		
		bnOri.setNode(m, LblockID, 0, vrootid, -1, null, null);
		
		
	       //���Ѻ󣬿���(n --��β)�Ľڵ㵽�½����ҽڵ�    	
		
		
		keys[0]=n;int[] tempss = new int[2];tempss[0] = blockID;		
		bnRoot.setNode(1, rightson, 0, 0, -1, keys, tempss);			
		return vrootid;	
	
	}
	
	public int splitNodeFirst(int blockID,int blockID2){
		
		int vrootid = 0;
		vrootid = addNode();
		BtreeNode bnRoot = new BtreeNode(vrootid);
		BtreeNode bnR = new BtreeNode(blockID2);
		BtreeNode bnL = new BtreeNode(blockID);
		int[] keys = new int[2];
		int[] pages = new int[2];		
		keys[0]=bnR.getKey(1);		pages[0]=blockID;		
		bnRoot.setNode(1, blockID2, 0, 0, 0, keys, pages);		
		int[] key = new int[bnR.getNum()-1];
		int[] page = new int[bnR.getNum()-1];
		for(int i =0;i<bnR.getNum()-1;i++){
			key[i] = bnR.getKey(i+1);
			page[i] = bnR.getPageNum(i+1);
		}		
		bnR.setNode(bnR.getNum()-1, -1, 0, vrootid, -1, key, page);
		bnL.setNode(-1, -1, -1, vrootid, -1, null, null);		
		return vrootid;
		
	}

	@Override
	public int combieNode(int blockID1, int blockID2) {
		// �˴��Ľڵ�ϲ������Ҳ������������ڵ�ĺϲ�������Ҫ��һ����Ԫ�ؽڵ����ڵ�ĺϲ�����Ҫ��Ϊ�˸����ڵ���������		
		int bnum1 ,i,key,page; //bnum1 Ϊ�ڵ�һ��Ԫ�ظ���ӵ��ֻ��һ��Ԫ�أ�key��Ϊ�ڵ�2 ��Ԫ��ֵ��pageΪ�ڵ�2����ָ��
		int[] keys1,keys2;    //keys1 Ϊ�ڵ�һ��������飬keys2Ϊ��ʱ����
		int[] pagenum1,pagenum2;   //pagenum1 Ϊ�ڵ�һ��ָ�����飬pagenum2Ϊ��ʱ����
		int  Lson = 0,Rson=0 ;	
		BtreeNode bn1 = new BtreeNode(blockID1);  
		BtreeNode bn2 = new BtreeNode(blockID2);		
		Btree bt = new Btree();		
		Lson = bn2.getPageNum(1);
		Rson = bn2.getRighson();
		bnum1 = bn1.getNum();   		
		keys1 = new int[bnum1];
		keys2 = new int[bnum1+1];		
		pagenum1 = new int[bnum1];
		pagenum2 = new int[bnum1+1];
		key = bn2.getKey(1);
		page = bn2.getPageNum(1);		
		//���ܽڵ��������в��������(��Ϊ���Ѻ������Խڵ�Ԫ��������Ϊ���)
		keys1 = bn1.getkey();
		pagenum1 = bn1.getPageNum();			
		for(i=0;(i<bnum1)&&(keys1[i]<key);i++){
				keys2[i] = keys1[i];	
				pagenum2[i] = pagenum1[i];
			}
		if(i==bnum1){
			bn1.setNode(-1, bn2.getRighson(), -1, -1, -1, null, null);
			keys2[i] = key;
			pagenum2[i] = page;
		}else {
			
			pagenum1[i] = bn2.getRighson();		
			
			keys2[i] = key;
			pagenum2[i] = page;
			for(;i<bnum1;i++){
				keys2[i+1] = keys1[i];
				pagenum2[i+1] = pagenum1[i];
			}
		}
		bn1.setNode(keys2.length, -1, -1, -1, -1, keys2, pagenum2);
		bt.setEmptyNode(blockID2,0);		
		
		
		BtreeNode bnL = new BtreeNode(Lson);  
		BtreeNode bnR = new BtreeNode(Rson);		
		bnL.setNode(-1, -1, -1, blockID1, -1, null, null);
		bnR.setNode(-1, -1, -1, blockID1, -1, null, null);
		return blockID1;
	}
	
	public void insertNode(int blockID,int i){
		Btree bt = new Btree();
		BtreeNode bn = new BtreeNode(blockID);
		int n = 0,j;
		int[] keys ;
		int[] keys2;
		
		if(bt.searchNode(blockID, i)!=0){
			System.out.println(i+"--exist!");
			return ;
		}				
		n = bn.getNum();			
		keys2 = new int[n+1];
		keys = new int[n];
		keys = bn.getkey();			
		for(j=0;j<n;j++){
			if(keys[j]>i)
				break;
			keys2[j]=keys[j];
		}
		if(keys2[j]!=i){
			keys2[j]=i;
			if(j!=n){
				for(;j!=n;j++){
					keys2[j+1]=keys[j];
				}
			}			
		}		
		bn.setNode(keys2.length, -1, -1, -1, -1,keys2,null);
	}
		
	
	@Override
	public void insert(int i) {
		Btree bt = new Btree();
		int blockid = 0;
		int check = 0;  
		int parent = 0; //��ʱ��Ǹ��ڵ�
		int insert = -1; //��ǲ���λ��
		int firstbi = 0; //Ҷ�ӽڵ���ѵ�����rootҳ��		

		blockid = bt.search(bt.getRootNum(), i);//���ҵ���ò����Ҷ�ӽڵ�
		check = bt.searchNode(blockid, i);	
		
		if(check != 0){
			return ;			
		}else{
				bt.insertNode(blockid, i);		
				
				BtreeNode bn = new BtreeNode(blockid);					
			
				if(bn.getNum()!=(k_n+1)){
					return ;
				}else {
					
					parent = bn.getParent();					
					firstbi = bt.splitNode(blockid);	
					
					if(parent!=0){
						insert = bn.getKey((k_n+1)/2+1);							
						bn = new BtreeNode(parent);	
					}

					
					while(bn.getNum()==k_n&&parent!=0){		
						
						if(bn.getKey(1)>insert){
							int temp = parent ;
							bn = new  BtreeNode(parent);
							temp = bn.getParent(); 	
							firstbi = bt.splitNodeFirst(blockid, parent);
							parent = temp;
						}else if(bn.getKey(bn.getNum())>insert){
								firstbi = bt.splitNodeInter(parent, insert, bn.getPageNum(1), bn.getRighson());
								parent = bn.getParent();
						}else{
							int temp = parent ;
							bn = new  BtreeNode(parent);
							temp = bn.getParent(); 							
							firstbi = bt.splitNode2(parent,firstbi);							
							parent = temp;
						}							
						bn = new  BtreeNode(parent);						
					}
					
					if(bn.getNum()!=k_n&&parent!=0){						
						 bt.combieNode(parent, firstbi);						
						return ;
					}		
					
					if(parent==0){
						bt.setRootNum(firstbi);
					}	
				}
		}
		return ;
	}


	@Override
	public int searchNode(int blockID,int key) {
		int i , n ,m=0;
		int[] keys ;
		boolean check = false;
		BtreeNode bn = new BtreeNode(blockID);
		n = bn.getNum();
		keys = new int[n+1];
		keys = bn.getkey();
		for(i=0;i<n;i++){
			if(keys[i]==key){
				check = true;
				m = i ;
			}
		}
		if(check)
			return m+1;
		else
			return 0;
	}

	@Override
	public int search(int blockID,int key) {
		BtreeNode bn = new BtreeNode(blockID);
		Btree bt = new Btree();
		int check = 0;
		if(bn.getOrleaf()==1){
				return blockID;
		}else {
			int[] keys = new int[bn.getNum()];
			int[] pagenums = new int[bn.getNum()];
			keys = bn.getkey(); 
			pagenums = bn.getPageNum();		
			if(key>=keys[bn.getNum()-1]){	
				check =bt.search(bn.getRighson(), key);
			}else {								
				for(int i =0;i<bn.getNum();i++){
					if(keys[i]>key){
						check = bt.search(pagenums[i], key);
						break;
					}
				}	
			}
			return check;
		}		
	}
	
	
	///////------------------------------------------->
	
	@Override
	public boolean delete(int i) {
		// TODO Auto-generated method stub
		int blockid=getRootNum();
		System.out.println("ͷ����"+blockid);
		int index;
		blockid=search(blockid,i);//i���ڵ�ҳ��
		System.out.println("i���ڵ�ҳ��blockid "+blockid);
		index=searchNode(blockid,i);//����i��block�е�λ��
		System.out.println("i����λ��index "+index);
		if(index==0){//����ʧ�ܣ������ڴ�Ҷ���
			System.out.println("�����ڴ�Ԫ��");
			return false;
		}
		
		BtreeNode btreenode=new BtreeNode(blockid);
		int num=btreenode.getNum();//��ǰ����Ԫ����
		int []key=btreenode.getkey();
		int []page=btreenode.getPageNum();
		
		if(num>Math.floor((BtreeNodeInterface.k_n+1)/2))//ɾ��֮����������С�����ֱ��ɾ��
		{
			int []newkey=movekey(key,index);
			int[] newpage=movekey(page,index);
			btreenode.setNode(num-1, -1, -1, -1, -1, newkey, newpage);
			System.out.println("ֱ��ɾ��ɹ�");
			return true;
		}
		int brother=btreenode.getBrother();
		BtreeNode brothernode=new BtreeNode(brother);
		int brothernum=brothernode.getNum();//ǰһ������Ԫ����
		
		int ybrother=btreenode.getRighson();//��һ������Ԫ����
		BtreeNode ybrothernode=new BtreeNode(ybrother);
		int ybrothernum=ybrothernode.getNum();
		
		int father=btreenode.getParent();//�õ����ڵ��ҳ��
		System.out.println("fatherID"+father);
		
		BtreeNode fathernode=new BtreeNode(father);
		System.out.println("fathernum"+fathernode.getNum());
		int [] fatherkey=fathernode.getkey();
		System.out.println("fatherkeylength---"+fatherkey.length);
		
		int []brotherkey=brothernode.getkey();
		
		int []brotherpage=brothernode.getPageNum();
		
		int []ybrotherkey=ybrothernode.getkey();
//		int []ybrotherpage=ybrothernode.getPageNum();
		if((brothernum+num-1>BtreeNodeInterface.k_n)&&(brothernum-1>=Math.floor((BtreeNodeInterface.k_n+1)/2)))//ǰһ�������Ԫ�ص�����������Сֵ��
		{//ȡ�����ߵ�Ԫ�ؼӵ�Ҫɾ��Ľ�������ߣ��޸ĸ��ڵ�Ԫ��
			int t=findinfather(fatherkey,i);
			fatherkey[t-1]=brotherkey[brothernum-1];
			delete(brotherkey[brothernum-1]);
			fathernode.setNode(-1, -1, -1, -1, -1, fatherkey, null);
			int []newkey=moveinsert(key,index,brotherkey[brothernum-1],0);
			int []newpage=moveinsert(page,index,brotherpage[brothernum-1],0);
			
			btreenode.setNode(num, -1, -1, -1, -1, newkey, newpage);
			System.out.println("ȡǰһ������Ԫ�أ�ɾ��ɹ�");
			return true;
		}
		else if((ybrothernum+num-1>BtreeNodeInterface.k_n)&&(ybrothernum-1>Math.floor((BtreeNodeInterface.k_n+1)/2)))//��һ�������Ԫ������������Сֵ
		{
			int t=findinfather(fatherkey,i);
			fatherkey[t]=ybrotherkey[0];
			delete(ybrotherkey[0]);
			fathernode.setNode(-1, -1, -1, -1, -1, fatherkey, null);
			int []newkey=moveinsert(key,index,ybrotherkey[0],1);
			int []newpage=moveinsert(page,index,ybrotherkey[0],1);
			btreenode.setNode(-1, -1, -1, -1, -1, newkey, newpage);
			
			System.out.println("ȡ��һ������Ԫ�أ�ɾ��ɹ�");
			return true;
		}
		else if((brothernum+num-1<=BtreeNodeInterface.k_n)&&(brothernum+num-1>=Math.floor((BtreeNodeInterface.k_n+1)/2)))
		{
			combieNode(brother,blockid,index,0);
			int t=findinfather(fatherkey,i);
			System.out.println("fatherkey.length"+fatherkey.length);
			System.out.println("fatherkey[0]"+fatherkey[0]);
			System.out.println("t"+t);
			delete(father,t);//ɾ��ڵ��е�Ԫ��
			
			System.out.println("��ǰһ�����ϲ���ɾ��ɹ�");
		}
		else if((ybrothernum+num-1<=BtreeNodeInterface.k_n)&&(ybrothernum+num-1>=Math.floor((BtreeNodeInterface.k_n+1)/2)))
		{
			combieNode(ybrother,blockid,index,1);
			int t=findinfather(fatherkey,i);
			delete(father,t+1);//ɾ��ڵ��е�Ԫ��
			System.out.println("���һ�����ϲ���ɾ��ɹ�");
		}
		
		
		return true;
	}
	
	@Override
	public boolean movekey(int blockID, int i) {//��ҳblockID��ɾ���i��key
		// TODO Auto-generated method stub
		BtreeNode btreenode=new BtreeNode(blockID);
		int [] key=btreenode.getkey();
		int [] pagenum=btreenode.getPageNum();
		int n=btreenode.getNum();
		
		int [] newkey=new int[n];
		int [] newpage=new int[n];
		for(int j=1;j<i;j++)
		{
			newkey[j]=key[j];
			newpage[j]=pagenum[j];
		}
		for(int j=i+1;j<=n;j++)
		{
			newkey[j-1]=key[j];
			newpage[j-1]=newpage[j];
		}
		if(i==n)
			btreenode.setNode(n-1, pagenum[n-1], -1, -1, -1, newkey, newpage);
		else
			btreenode.setNode(n-1, -1, -1, -1, -1, newkey, newpage);
		return true;
	}

	@Override
	public boolean delete(int blockID, int i) {//ɾ���Ҷ����еĵ�i��Ԫ��
		// TODO Auto-generated method stub
		BtreeNode btreenode=new BtreeNode(blockID);
		int num=btreenode.getNum();
		int []key=btreenode.getkey();
		int []page=btreenode.getPageNum();
		System.out.println("blockID"+blockID);
		
		System.out.println(Math.floor((BtreeNodeInterface.k_n+1)/2.0)-1);
		System.out.println(Math.ceil((BtreeNodeInterface.k_n+1)/2.0)-1);
		if(num-1>Math.ceil((BtreeNodeInterface.k_n+1)/2)-1||(getRootNum()==blockID))//Ҫɾ���Ԫ�����ڵĽ�������������Сֵ
		{																//ֱ��ɾ��Ԫ�أ�ɾ�����������СֵҪ��
			if(num-1==0)//��fathernode��root��ɾ���㣬Ψһ�ĺ��ӳ�Ϊroot
			{
				System.out.println("page"+btreenode.getPageNum(i));
				System.out.println("page[0]"+page[0]);
				System.out.println("i"+i);
				setRootNum(page[i-1]);
				System.out.println("root ID...."+getRootNum());
				setEmptyNode(blockID);
				System.out.println("delete root success!");
				return true;
			}
				page[i]=page[i-1];
				page[i-1]=0;
				key[i-1]=0;
				int newkey[]=new int[num-1];
				int newpage[]=new int[num-1];
				for(int j=0;j<num-1;j++)
				{
					if(j<i-1)
					{
						newkey[j]=key[j];
						newpage[j]=page[j];
					}
					else
					{
						newkey[j]=key[j+1];
						newpage[j]=page[j+1];
					}
				}
				btreenode.setNode(num-1, -1, -1, -1, -1, newkey, newpage);
				System.out.println("ֱ��ɾ���Ҷ�ڵ��е�Ԫ�سɹ���");
			return true;
		}
		int brotherid=btreenode.getBrother();
		BtreeNode brothernode=new BtreeNode(brotherid);
		int brothernum=brothernode.getNum();
		int []brotherkey=brothernode.getkey();
		int []brotherpage=brothernode.getPageNum();
		
		
		
		int father=btreenode.getParent();
		BtreeNode fathernode=new BtreeNode(father);
		int []fatherkey=fathernode.getkey();
		int []fatherpage=fathernode.getPageNum();
		
		int tt=findinfather(fatherkey,btreenode.getKey(i));
		int ybrother;
		if(tt+1>=fathernode.getNum())
			ybrother=fathernode.getRighson();
		else
			ybrother=fatherpage[tt+1];
		//int ybrother=btreenode.getBrother();
		BtreeNode ybrothernode=new BtreeNode(ybrother);
		int ybrothernum=ybrothernode.getNum();
		int []ybrotherkey=ybrothernode.getkey();
		int []ybrotherpage=ybrothernode.getPageNum();
		if(brothernum+num-1+1<=BtreeNodeInterface.k_n)//���Ժϲ���ǰһ����㣬�Ӹ��ڵ��һ��Ԫ��
		{			
			page[i]=page[i-1];
			page[i-1]=0;
			key[i-1]=0;
			int newkey[]=new int[num-1];
			int newpage[]=new int[num-1];
			for(int j=0;j<num-1;j++)
			{
				if(j<i-1)
				{
					newkey[j]=key[j];
					newpage[j]=page[j];
				}
				else
				{
					newkey[j]=key[j+1];
					newpage[j]=page[j+1];
				}
			}
			int t=findinfather(fatherkey,btreenode.getKey(i));
			btreenode.setNode(num-1, -1, -1, -1, -1, newkey, newpage);
			setEmptyNode(blockID,0);
			int []newbrotherkey=new int[brothernum+1+num-1];
			int []newbrotherpage=new int[brothernum+1+num-1];
			
			
			
			for(int j=0;j<brothernum;j++)
			{
				newbrotherkey[j]=brotherkey[j];
				newbrotherpage[j]=brotherpage[j];
			}
			newbrotherkey[brothernum]=fatherkey[t-1];
			newbrotherpage[brothernum]=brothernode.getRighson();
			
			int l=brothernum+1;
			for(int j=0;j<num-1;j++)
			{
				newbrotherkey[j+l]=newkey[j];
				newbrotherpage[j+l]=newpage[j];
				l++;
			}
			brothernode.setNode(brothernum+num, btreenode.getRighson(), -1, -1, -1, newbrotherkey, newbrotherpage);
			System.out.println("combie with before node!");
			delete(father,t);
			return true;
		}
		if(ybrothernum+num-1+1<=BtreeNodeInterface.k_n)//���Ժϲ�����һ����㣬�Ӹ��ڵ��һ��Ԫ��
		{
			page[i]=page[i-1];
			page[i-1]=0;
			key[i-1]=0;
			int newkey[]=new int[num-1];
			int newpage[]=new int[num-1];
			for(int j=0;j<num-1;j++)
			{
				if(j<i-1)
				{
					newkey[j]=key[j];
					newpage[j]=page[j];
				}
				else
				{
					newkey[j]=key[j+1];
					newpage[j]=page[j+1];
				}
			}
			btreenode.setNode(num-1, -1, -1, -1, -1, newkey, newpage);
			setEmptyNode(blockID,0);
			int []newbrotherkey=new int[ybrothernum+1+num-1];
			int []newbrotherpage=new int[ybrothernum+1+num-1];
			
			
			int t=findinfather(fatherkey,btreenode.getKey(i));
			
			for(int j=0;j<num-1;j++)
			{
				newbrotherkey[j]=newkey[j];
				newbrotherpage[j]=newpage[j];
			}
			newbrotherkey[num-1]=fatherkey[t];
			newbrotherpage[num-1]=btreenode.getRighson();
			
			int l=num;
			for(int j=0;j<ybrothernum;j++)
			{
				newbrotherkey[j+l]=ybrotherkey[j];
				newbrotherpage[j+l]=ybrotherpage[j];
				//l++;
			}
			ybrothernode.setNode(ybrothernum+num, -1, -1, -1, btreenode.getBrother(), newbrotherkey, newbrotherpage);
			System.out.println("combie with after node!");
			delete(father,t+1);
			return true;
		}
		if(brothernum+num>BtreeNodeInterface.k_n&&ybrothernum+num>BtreeNodeInterface.k_n)
		{//������ǰһ���ͺ�һ�����ϲ����Ӹ��ڵ��һ��Ԫ��
			int t=findinfather(fatherkey,btreenode.getKey(i));
			page[i]=page[i-1];
			/*for(int j=0;j<i-1;j++)
			{
				page[j]=page[j];
				key[j]=key[j];
			}*/
			for(int j=i-1;j>0;j--)
			{
				page[j]=page[j-1];
				key[j]=key[j-1];
			}
			key[0]=fatherkey[t-1];
			page[0]=brothernode.getRighson();
			BtreeNode rightson=new BtreeNode(brothernode.getRighson());
			int []rightkey=rightson.getkey();
			fatherkey[t-1]=rightkey[0];
			btreenode.setNode(num, -1, -1, -1, -1, key, page);
			fathernode.setNode(-1, -1, -1, -1, -1, fatherkey, null);
			System.out.println("borrow a key form father root!");
			brotherkey=movekey(brotherkey,brothernum);
			brotherpage=movekey(brotherpage,brothernum);
			brothernode.setNode(brothernum-1,brotherpage[brothernum-1] , -1, -1, -1, brotherkey, brotherpage);
		}
		return true;
	}

	@Override
	public boolean combieNode(int existid, int deleteid, int i,int flag) {
		// TODO Auto-generated method stub
		BtreeNode existnode=new BtreeNode(existid);
		int existnum=existnode.getNum();
		int []existkey=existnode.getkey();
		int []existpage=existnode.getPageNum();
		
		BtreeNode deletenode=new BtreeNode(deleteid);
		int deletenum=deletenode.getNum();
		int []deletekey=deletenode.getkey();
		int []deletepage=deletenode.getPageNum();
		
		int []newkey=movekey(deletekey,i);
		int []newpage=movekey(deletepage,i);
		
		int []keyarray=join(existkey,newkey);
		int []pagearray=join(existpage,newpage);
		if(flag==0)//ǰ�ƶ�
		{
			existnode.setNode(existnum+deletenum-1, deletenode.getRighson(), -1, -1, -1, keyarray, pagearray);
		}
		else
		{
			int brotherid=deletenode.getBrother();
			existnode.setNode(existnum+deletenum-1, -1, -1, -1, brotherid, keyarray, pagearray);
		}
		setEmptyNode(deleteid,0);//���ñ�ɾ��Ľ��Ϊ�ս��
		
		
		return true;
	}

	@Override
	public int[] movekey(int[] key, int index) {//��key��ɾ���index��Ԫ�أ�key����-1
		// TODO Auto-generated method stub
		int length=key.length;
		int []newnode=new int[length-1];
		for(int j=0;j<index-1;j++)
		{
			newnode[j]=key[j];
		}
		for(int j=index-1;j<length-1;j++)
		{
			newnode[j]=key[j+1];
		}
		return newnode;
	}

	@Override
	public int[] moveinsert(int[] key, int index, int i, int flag) {//ɾ��Key�е�index��Ԫ�أ�����i�鵽key�ײ���flag=0����β����flag=1��
		// TODO Auto-generated method stub
		int length=key.length;
		if(flag==0)//�����ײ���index֮ǰ����ݺ���
		{
			for(int j=index-1;j>=1;j--)
			{
				key[j]=key[j-1];
			}
			key[0]=i;
		}
		else//����β����index֮������ǰ��
		{
			for(int j=index-1;j<length-1;j++)
			{
				key[j]=key[j+1];
			}
			key[length-1]=i;
		}
		return key;
	}

	@Override
	public int findinfather(int[] key, int i) {//��key���ҵ�С��i��������λ�ã���j��Ԫ��
		// TODO Auto-generated method stub
		int t=0;
		System.out.println("key.length"+key.length);
		for(int j=0;j<key.length;j++)
		{
			if(key[j]<=i)
			{
				t++;
				continue;
			}
		}
		return t;
	}

	@Override
	public int[] join(int[] before, int[] after) {
		// TODO Auto-generated method stub
		int blength=before.length;
		int alength=after.length;
		int []newarray=new int[blength+alength];
		for(int i=0;i<blength;i++)
		{
			newarray[i]=before[i];
		}
		int t=0;
		for(int i=0;i<alength;i++)
		{
			newarray[blength+t]=after[i];
			t++;
		}
		return newarray;
	}
	
}
